Software that is designed to run on multicore and manycore processors (also known as Chip Multiprocessors (CMP)) must be explicitly structured for correctness in the presence of concurrent execution. Most multicore processors today support a programming model of coherent shared memory whereby multiple threads, belonging to the same process, can access the same address space and data variables therein. Furthermore, different threads can execute concurrently on different cores on the same multicore processor. The underlying hardware is responsible for ensuring a consistent view of memory for each of the threads in the process. This hardware model is known as Symmetric Multi-Processing (SMP) and is commonplace in today's multicore machines
FIG. 1 illustrates a conventional multicore processor system having a shared memory programming model that includes a synchronization mechanism to coordinate accesses from different threads to the same data location in order to give consistent and correct results. In the prior art a programmer would manually declare and associate a lock with each variable, which creates a potential source of error. Additionally, a hash table or other lookup table structure was typically required to resolve the relationship between locks and variables. In the traditional way to use locks, locks are predefined and it is not easy to use the “correct” lock because of the difficulties of tracking the relation between locks and variables. Moreover, the traditional way to use locks is error-prone (due to incorrect lock selection or failing to take or release the lock at the appropriate time) causing many kinds of errors such as: races, atomicity violations or deadlocks.
An important element of correctness within a shared memory environment is ensuring that accesses to data are serialized in order to ensure atomicity in data writes. For example, suppose that Thread A (running on core 0) is writing a 64-bit aligned integer (e.g., a variable ‘v’) in memory (on a 32-bit machine) such that two memory operations/transactions on the memory controller are needed for Thread A to complete the write. Without correct synchronization, a Thread B might read the first half of the memory location before Thread A has completed writing the second half—this would give an inconsistent and incorrect result. To avoid this problem, read and write access to variable ‘v’ should be synchronized through some form of concurrency mechanism (e.g., spinlock, mutex, or semaphore) that can be realized on a specific processor.
Synchronization mechanisms can be implemented as language-level constructs (e.g., Java®'s synchronized keyword) or as a call to a library (e.g., a POSIX pthread library). In both cases the programmer must explicitly identify the allocation of the locks. In addition to allocating the locks, the programmer must in general reference the locks through compile-time symbols.
Below is an example of typical lock protection in the C programming language:
#include <pthread.h>. . .int shared_data;pthread_mutex_t shared_data_lock =PTHREAD_MUTEX_INITIALIZER;/* static lock initialization */void func( ){/* take lock */pthread_mutex_lock(&shared_data_lock);/* safe access data */shared_data ++;/* release lock */pthread_mutex_unlock(&shared_data_lock);}
In this example of lock protection, there must be a known relationship between a lock and the corresponding piece of shared data that it is protecting (i.e., that the shared_data_lock protects shared_data). The only thing that assures that the correct locks are being taken for access to a given shared data variable is the diligence of the programmer.
Tracking lock-variable relationships is difficult for the programmer especially when locks have been declared separately from the point of variable access. There are some commercial products that allow the inclusion of code annotations to aid in the formal specification of relationships and thus allow machine-based verification of correct lock usage via static analysis. Nevertheless, this approach cannot be easily realized within the context of an off-the-shelf compiler such as GNU C/C++.
The present invention was developed in view of the above-described problems in the prior art in regards to lock and allocation and lock resolution.